package com.lft.sort02.selection_sort;

import java.util.Arrays;

public class SelectionSort {
	public static void main(String[] args) {
		int[] a = {101, 34, 119, 1};
		System.out.println(Arrays.toString(selectionSort(a)));
	}
	
	public static int[] selectionSort(int[] a) {
		// 使用逐步推导的方式来，讲解选择排序
		// 算法 先简单 -> 再复杂，就是可以把一个复杂的算法，拆分成简单的问题 -> 逐步解决
		// 原始数组：101,34,119,1
		// 选择排序的时间复杂度：平均：O(n^2)，最差：O(n^2)
		for (int j = 0; j < a.length - 1; j++) {
			int minIndex = j;
			int min = a[j];
			for (int i = j + 1; i < a.length; i++) {
				// 说明假定的不是最小值。
				if (a[i] < min) {
					minIndex = i;
					min = a[i];
				}
			}
			// 交换。
			if (minIndex != j) {
				a[minIndex] = a[j];
				a[j] = min;
			}
		}
		return a;
		
		// // 第 1 轮：1,34,119,101
		// int minIndex = 0;
		// int min = a[0];
		// for (int i = 0 + 1; i < a.length; i++) {
		// 	// 说明假定的不是最小值。
		// 	if (a[i] < min) {
		// 		minIndex = i;
		// 		min = a[i];
		// 	}
		// }
		// // 交换。
		// if (minIndex != 0) {
		// 	a[minIndex] = a[0];
		// 	a[0] = min;
		// }
		//
		// // 第 2 轮：1,34,119,101
		// minIndex = 1;
		// min = a[1];
		// for (int i = 0 + 1 + 1; i < a.length; i++) {
		// 	// 说明假定的不是最小值。
		// 	if (a[i] < min) {
		// 		minIndex = i;
		// 		min = a[i];
		// 	}
		// }
		// if (minIndex != 1) {
		// 	// 交换。
		// 	a[minIndex] = a[1];
		// 	a[1] = min;
		// }
		//
		// // 第 3 轮：1,34,119,101
		// minIndex = 2;
		// min = a[2];
		// for (int i = 0 + 1 + 1; i < a.length; i++) {
		// 	// 说明假定的不是最小值。
		// 	if (a[i] < min) {
		// 		minIndex = i;
		// 		min = a[i];
		// 	}
		// }
		// if (minIndex != 2) {
		// 	// 交换。
		// 	a[minIndex] = a[2];
		// 	a[2] = min;
		// }
		// return a;
	}
}
